/// 双指针问题




/// https://leetcode.cn/problems/move-zeroes/?envType=study-plan-v2&envId=top-100-liked
/// 283. 移动零
/// 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
/// 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
pub fn move_zeroes(nums: &mut Vec<i32>) {
    let mut last = nums.len() - 1;
    for (mut i, &v) in nums.iter().rev().enumerate() {
        let total = nums.len() - 1;
        i = total - i;
        if v == 0 {
            if i + 1 <= last {
                exchange_between(nums, i, i, i + 1, last);
            }
            last -= 1;
        }
    }
    #[allow(invalid_reference_casting)]
    fn exchange_between(nums: &Vec<i32>, a: usize, b: usize, c: usize, d: usize) {
        unsafe { (&mut *(nums as *const _ as *mut Vec<i32>))[a..=b].reverse(); }
        unsafe { (&mut *(nums as *const _ as *mut Vec<i32>))[c..=d].reverse(); }
        unsafe { (&mut *(nums as *const _ as *mut Vec<i32>))[a..=d].reverse(); }
    }
}

/// TIP 考虑使用双指针，将0元素冒泡出去
pub fn move_zeroes2(nums: &mut Vec<i32>) {
    let mut l = 0;
    let mut r = 0;
    while l < nums.len() {
        if r >= nums.len() {
            nums[l] = 0;
            l += 1;
            continue;
        }
        if nums[r] != 0 {
            nums[l] = nums[r];
            l += 1;
        }
        r += 1;
    }
}


#[test]
pub fn test_move_zeroes() {
    println!("{:?}", move_zeroes2(&mut vec![0, 1, 0, 3, 12, 0]));
}

/// https://leetcode.cn/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-100-liked
/// 11. 盛最多水的容器
// 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
// 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
// 返回容器可以储存的最大水量。
// 说明：你不能倾斜容器。
/// TIP: 双指针法，由于容器面积由最小短板决定，
/// 每次遍历时如果只移动左右板中的短板，下次容器面积可能大于或者小于原有容器面积
/// 每次遍历时如果只移动左右板中的长板，下次容器面积一定小于等于原有容器面积（排除无效的移动）
pub fn max_area(height: Vec<i32>) -> i32 {
    let mut a = 0;
    let mut b = height.len() - 1;
    let mut max = 0;
    while a < b {
        if height[a] < height[b] {
            max = std::cmp::max(max, height[a] * (b - a) as i32);
            a += 1;
        } else {
            max = std::cmp::max(max, height[b] * (b - a) as i32);
            b -= 1;
        }
    }
    max
}

#[test]
pub fn test_max_area() {
    println!("{:?}", max_area(vec![1, 8, 6, 2, 5, 4, 8, 3, 7]));
}

/// https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked
/// 15. 三数之和
// 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
// 你返回所有和为 0 且不重复的三元组。
// 注意：答案中不可以包含重复的三元组。
//
// TIP: 考虑到排序减少迭代重复情况，将a+b+c=0 转化成 -a=b+c
pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut result = vec![];
    let mut nums = nums.clone();
    nums.sort();


    let jump = |index: &mut usize, forward: bool| {
        let before = nums[*index];
        loop {
            if before != nums[*index] { break; }
            if forward {
                if *index == nums.len() - 1 { break; }
                *index = std::cmp::min(nums.len() - 1, *index + 1);
            } else {
                if *index == 0 { break; }
                *index = std::cmp::max(0, *index - 1);
            }
        }
    };


    for (i, &v) in nums.iter().enumerate() {
        if i == 0 || v != nums[i - 1] {
            let mut l = i + 1;
            let mut r = nums.len() - 1;
            let target = -nums[i];
            while l < r {
                if nums[l] + nums[r] > target {
                    r -= 1;
                } else if nums[l] + nums[r] < target {
                    l += 1;
                } else {
                    result.push(vec![nums[i], nums[l], nums[r]]);
                    while r - 1 > 0 {
                        r -= 1;
                        if nums[r + 1] != nums[r] {
                            break;
                        }
                    }
                    while l + 1 < nums.len() {
                        l += 1;
                        if nums[l - 1] != nums[l] {
                            break;
                        }
                    }
                }
            }
        }
    }

    result
}

#[test]
pub fn test_three_sum() {
    println!("{:?}", three_sum(vec![-1, 0, 1, 2, -1, -4]));
}

/// https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-100-liked
/// 42. 接雨水
/// 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
///
// TIP: 接多少雨水是固定的，每个单位的雨水 (leftMax-height[left]) , (rightMax-height[max])
// 确定了左右最大板之后，每次水柱的获取由最小板决定
pub fn trap(height: Vec<i32>) -> i32 {
    let mut total = 0;
    let mut l = 0;
    let mut r = height.len() - 1;
    let mut lm = 0;
    let mut rm = 0;
    while l < r {
        lm = std::cmp::max(lm, height[l]);
        rm = std::cmp::max(rm, height[r]);
        if height[l] < height[r] {
            total += lm - height[l];
            l += 1;
        } else {
            total += rm - height[r];
            r -= 1;
        }
    }
    total
}

#[test]
pub fn test_trap() {
    println!("{:?}", trap(vec![0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]));
}
